package com.fengye.algorithms.huawei.dp;

import java.util.Scanner;

/**
 * @Author fengye
 * @Date 2023/4/7 10:48
 **/
public class RabbitNumber {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            System.out.println(rabbit(a));
            System.out.println(rabbitv2(a));
        }
    }

    public static long rabbitv2(int n) {
        if (n <= 2) {
            return 1;
        }
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }

        return dp[n];
    }

    public static int rabbit(int n) {
        if(n<=2) {
            return 1;
        }
        return rabbit(n-1) + rabbit(n-2);
    }
}
